package _03_链表;

import _01_第一季._00_公共接口.AbstractList;

/*
    双向循环链表的实现
 */
public class CirCleLinkedList<E> extends AbstractList<E> {

    private Node<E> first; //头指针，指向链表的第一个有效节点
    private Node<E> last; //尾指针，指向链表的最后一个有效节点


    //静态内部节点类
    private static class Node<E>{
        E element; //内部存储的数据
        Node<E> prev; //存储上一个节点的地址
        Node<E> next; //存储下一个节点的地址

        public Node(){
            this(null,null,null);
        }
        public Node(E element){
            this(null,element,null);
        }
        //内部构造方法
        public Node(Node<E> prev, E element, Node<E> next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();

            if(prev!=null){
                sb.append(prev.element);
            }else{
                sb.append("null");
            }
            sb.append("_").append(element).append("_");

            if(next!=null){
                sb.append(next.element);
            }else {
                sb.append("null");
            }
            return sb.toString();
        }
    }

    //内部寻找节点的方法
    private Node<E> node(int index){
        rangeCheck(index);

        //从头指针开始找
        if (index < (size >> 1)) {
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else { //从尾结点开始找
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }

    //指定索引处添加元素
    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        if(index==size){ //在链表尾部添加
            Node<E> oldLast = last;//拿到之前的尾结点
            //创建新的尾结点并将尾指针移动到新的尾结点
            last = new Node<>(oldLast,element,first);
            if(oldLast==null){ //当链表为空时，第一次添加节点的时候
                first = last;
                first.next = first;
                first.prev = first;
            }else{
                oldLast.next = last;
                first.prev = last;
            }

        }else{ //在链表头部 和 链表中间添加
            //待添加元素的下一个
            Node<E> next = node(index);
            //待添加元素的上一个
            Node<E> prev = next.prev;
            //新添加的元素,节点的两根线连好
            Node<E> node = new Node<>(prev, element, next);
            prev.next = node;
            next.prev = node;
            if(next==first){ //添加在头节点的时候 index == 0
                first = node;
            }
        }
        size++;
    }

    @Override
    public E get(int index) {
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E ret = node.element;
        node.element = element;
        return ret;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);

        Node<E> node = first;
        if(size==1){ //当链表仅有一个节点
            first = null;
            last = null;
        }else {
            //待删除节点
            node = node(index);
            Node<E> prev = node.prev;//待删除节点的上一个
            Node<E> next = node.next; //待删除节点的下一个
            prev.next = next; //跳过node节点
            next.prev = prev;

            if(node==first){ // index == 0
                first = next; //头指针向下移动一位
            }
            if(node==last){  // index = size-1;
                last = prev;
            }
        }
        size--;
        return node.element;
    }

    @Override
    public void remove(E element) {
        int index = indexOf(element);
        if(index!=ELEMENT_NOT_FOUND){
            remove(index);
        }
    }

    @Override
    public int indexOf(E element) {
        Node<E> node = first; //从头结点开始遍历
        for(int i=0;i<size;++i){
            if(valEquals(element,node.element)) return i;
            node = node.next;
        }
        return ELEMENT_NOT_FOUND;
    }
    private boolean valEquals(Object v1,Object v2){
        return (v1 == v2) || (v1 != null && v1.equals(v2));
    }

    @Override
    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }

            string.append(node);

            node = node.next;
        }
        string.append("]");
        return string.toString();
    }
}
